package zuoshen_video2.dynamic;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collector;
import java.util.stream.Collectors;

import org.junit.Test;

//两个人玩游戏，依次从数组拿到一个数，最终分数大的赢；【两人都很鸡贼】
public class MaxPoints {
    
    // 1. 单递归
    public int[] whoWin(int[] nums) {
        Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());

        int[] res =  dfs(true, 0, 0, set);
        return res;
    }

    public int[] dfs(boolean aTurn, int a, int b, Set<Integer> set) {
        if (set.isEmpty()) return new int[]{a, b};
        Set<Integer> newSet = new HashSet<>(set);
        int[] ans = new int[2];
        if (aTurn) {
            int res = 0;
            for (int s: set) {
                // a选择一个拿了
                newSet.remove(s);
                int[] cur = dfs(false, a + s, b, newSet);
                if (cur[0] > res) {
                    res = cur[0];
                    ans[0] = cur[0];
                    ans[1] = cur[1];
                }
                newSet.add(s);
            }
        } else {
            int res = Integer.MAX_VALUE;
            for (int s: set) {
                // b选择一个拿了,想要a得到尽量小的结果
                newSet.remove(s);
                int[] cur = dfs(true, a, b + s, newSet);
                if (cur[0] < res) {
                    res = cur[0];
                    ans[0] = cur[0];
                    ans[1] = cur[1];
                }
                newSet.add(s);
               
            }
        }
        return ans;
    }

    @Test
    public void test1() {
        int[] nums = {3, 100, 2, 50, 300};
        System.err.println(Arrays.toString(whoWin(nums)));
    }


    //想改为动态规划，必须满足一个条件，每次只能取两边元素中的一个，即边界动态规划
    public int whoWin2(int[] nums) {
        int len = nums.length;
        //f1[i][j] 表示a在[i, j]范围内所能获取的最大值
        int[][] f1 = new int[len][len];
        //f2[i][j] 表示a在[i, j]。。。最小值。
        int[][] f2 = new int[len][len];

        for (int i = 0; i < len; i++) {
                //只有一个元素，a的回合就a拿，b的回合就b拿
            f1[i][i] = nums[i]; 
            f2[i][i] = 0;
        }
        for (int i = len - 2; i >= 0; i--) {
           for (int j = i + 1; j < len; j++) {
                f1[i][j] = Math.max(f2[i][j - 1] + nums[j], f2[i + 1][j] + nums[i]);
                f2[i][j] = Math.min(f1[i][j - 1], f1[i + 1][j]);      
           }
        }
        System.out.println(f1[0][len - 1] + " " + f2[0][len - 1]);
        return Math.max(f1[0][len - 1], f2[0][len - 1]);
    }

    @Test
    public void test2() {
        int[] nums = {3, 100, 2, 50, 300};
        System.err.println(whoWin2(nums));
    }
}
